/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package main;

import JaCoP.constraints.*;
import JaCoP.core.IntVar;
import JaCoP.core.Store;
import JaCoP.search.*;
import java.util.ArrayList;

/**
 *
 * @author sbavdhorst
 */
public class Solver {
    
    //tries to generate a circle, by checking every possible circle
    public static Circle bruteForce(ArrayList<Quartet> quartets, int size){
        Circle circle = new Circle(size);
        
        ArrayList<char[]> permutations = permutations(DenseSetGenerator.generateAlphabet(size));
        for(char[] ordering: permutations){
            circle.add(ordering);
            if(checkAllQuartets(quartets, circle))
                return circle;
            else
                circle.clear();
        }
        return circle;
        
    }
    
    //after obtaining all possible sets, use this methods to check what lists can be put on a circle in a brute force way
    public static ArrayList<ArrayList<Quartet>> checkAll(ArrayList<ArrayList<Quartet>> allLists, int size){
        ArrayList<ArrayList<Quartet>> newList = new ArrayList<>();
        for(ArrayList<Quartet> list: allLists){
            if(bruteForce(list, size).getCircle().get(0) != '\u0000')
                newList.add(list);
        }
        return newList;
    }
    
    //check for every quartet if it is on the circle
    public static boolean checkAllQuartets(ArrayList<Quartet> quartets, Circle circle){
        boolean ok = true;
        for(Quartet q: quartets){
            if(!q.isOnCircle(circle)){
                ok = false;
            }
        } 
        return ok;
    }
    
    private static ArrayList<char[]> permutations(char[] alphabet){
        ArrayList<char[]> permutations = new ArrayList<>();
        if(alphabet.length <= 1)
            permutations.add(alphabet);
        else{
            ArrayList<char[]> permutations1 = permutations(deleteLast(alphabet));
            char c = alphabet[alphabet.length-1];
            for(char[] list: permutations1){
                for(int i = 1; i<alphabet.length; i++){
                    permutations.add(insert(list, c, i));
                }
            }
        }
        return permutations;
    }
    
    public static Circle constraintProgramming(ArrayList<Quartet> quartets, int size){
        Circle circle = new Circle(size);
        
        Store store = new Store();
        IntVar[] vars = new IntVar[size];
        for(int i = 0; i<size; i++)
            vars[i] = new IntVar(store, Character.toString((char)(i+97)), 1, size);
        
        for(Quartet q: quartets){
            //imagine you have quartet ab|cd
            //actual quartet may be different
            //97 is a so "a-97 = 0"
            IntVar a = vars[q.getPair1()[0]-97];
            IntVar b = vars[q.getPair1()[1]-97];
            IntVar c = vars[q.getPair2()[0]-97];
            IntVar d = vars[q.getPair2()[1]-97];
            
            //first: ab = a < b etc..
//            PrimitiveConstraint ab = new XltY(a, b);
            PrimitiveConstraint ac = new XltY(a, c);
            PrimitiveConstraint ad = new XltY(a, d);
//            PrimitiveConstraint ba = new XltY(b, a);
            PrimitiveConstraint bc = new XltY(b, c);
            PrimitiveConstraint bd = new XltY(b, d);
            PrimitiveConstraint ca = new XltY(c, a);
            PrimitiveConstraint cb = new XltY(c, b);
//            PrimitiveConstraint cd = new XltY(c, d);
            PrimitiveConstraint da = new XltY(d, a);
            PrimitiveConstraint db = new XltY(d, b);
//            PrimitiveConstraint dc = new XltY(d, c);
            
            //first: ordering acbd cannot happen, so not(a<c and a<b and a<d and c<b and c<d and b<d) etc..
            store.impose(new Not(new And(new PrimitiveConstraint[]{ac, cb, bd})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{ad, db, bc})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{bc, ca, ad})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{bd, da, ac})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{ca, ad, db})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{cb, bd, da})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{da, ac, cb})));
            store.impose(new Not(new And(new PrimitiveConstraint[]{db, bc, ca})));
        }
        
        Constraint different = new Alldifferent(vars); 
        store.impose(different);
        
        //consistency check but if this is true, it still could be that it's inconsistent
        if(!store.consistency())
            return circle;
        
        Search<IntVar> label = new DepthFirstSearch<>(); 
        SelectChoicePoint<IntVar> select = new SimpleSelect<>(vars, new SmallestDomain<IntVar>(), new IndomainMin<>()); 
        if(!label.labeling(store, select))
            return circle;
        
        ArrayList<Character> circ = new ArrayList<>();
        for(int i = 0; i<size; i++)
            circ.add('0');
        
        for(int j = 0; j<size; j++)
            circ.set(vars[j].value()-1,(char) (j+97));

        return new Circle(circ);
    }
    
    public static Circle separatedConstraint(ArrayList<Quartet> quartets, int size){
        Circle circle = new Circle(size);
        
        //first make 2 lists, 1 where there is 1 quartet for those 4 taxa, the other 2 quartets for those 4 taxa
        ArrayList<Quartet> one = new ArrayList<>();
        ArrayList<Quartet> two = new ArrayList<>();
        for(int i = 0; i<quartets.size(); i++){
            for(int j = i+1; j<quartets.size(); j++){
                if(quartets.get(i).sameTaxa(quartets.get(j))){
                    two.add(quartets.get(i));
                    two.add(quartets.get(j));
                }
            }
            if(!two.contains(quartets.get(i)))
                one.add(quartets.get(i));
        }
        
        if(one.size() + two.size() != quartets.size())
            System.out.println("Separated error!");
        
        //setup the constraint program
        Store store = new Store();
        IntVar[] vars = new IntVar[size];
        for(int i = 0; i<size; i++)
            vars[i] = new IntVar(store, Character.toString((char)(i+97)), 1, size);
        
        //for the quartets in one, add the "not" constraints
        if(one.size() > 0){
            for(Quartet q: one){
                //imagine you have quartet ab|cd
                //actual quartet may be different
                //97 is a so "a-97 = 0"
                IntVar a = vars[q.getPair1()[0]-97];
                IntVar b = vars[q.getPair1()[1]-97];
                IntVar c = vars[q.getPair2()[0]-97];
                IntVar d = vars[q.getPair2()[1]-97];

                //first: ab = a < b etc..
                PrimitiveConstraint ac = new XltY(a, c);
                PrimitiveConstraint ad = new XltY(a, d);
                PrimitiveConstraint bc = new XltY(b, c);
                PrimitiveConstraint bd = new XltY(b, d);
                PrimitiveConstraint ca = new XltY(c, a);
                PrimitiveConstraint cb = new XltY(c, b);
                PrimitiveConstraint da = new XltY(d, a);
                PrimitiveConstraint db = new XltY(d, b);

                //first: ordering acbd cannot happen, so not(a<c and c<b and b<d) etc..
                store.impose(new Not(new And(new PrimitiveConstraint[]{ac, cb, bd})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{ad, db, bc})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{bc, ca, ad})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{bd, da, ac})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{ca, ad, db})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{cb, bd, da})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{da, ac, cb})));
                store.impose(new Not(new And(new PrimitiveConstraint[]{db, bc, ca})));
            }
        }
        
        if(two.size() > 0){
            for(int i = 0; i<two.size(); i = i+2){
                char a = 0, b=0, c=0, d=0;
                // the ordering on the circle is: a b d c
                    if(two.get(i+1).pairContains(true,two.get(i).getPair1()[0]))
                        a = two.get(i).getPair1()[0];
                    else if(two.get(i+1).pairContains(true,two.get(i).getPair1()[1]))
                        a = two.get(i).getPair1()[1];

                    if(two.get(i).getPair1()[0] != a)
                        b = two.get(i).getPair1()[0];
                    else if(two.get(i).getPair1()[1] != a)
                        b = two.get(i).getPair1()[1];

                    if(two.get(i+1).getPair1()[0] != a)
                        c = two.get(i+1).getPair1()[0];
                    else if(two.get(i+1).getPair1()[1] != a)
                        c = two.get(i+1).getPair1()[1];

                    if(two.get(i).getPair2()[0] != a && two.get(i).getPair2()[0] != b && two.get(i).getPair2()[0] != c)
                        d = two.get(i).getPair2()[0];
                    else if(two.get(i).getPair2()[1] != a && two.get(i).getPair2()[1] != b && two.get(i).getPair2()[1] != c)
                        d = two.get(i).getPair2()[1];
                    
                IntVar a1 = vars[a-97];
                IntVar b1 = vars[b-97];
                IntVar c1 = vars[c-97];
                IntVar d1 = vars[d-97];
                
                PrimitiveConstraint ab = new XltY(a1, b1);
                PrimitiveConstraint ac = new XltY(a1, c1);
                PrimitiveConstraint ba = new XltY(b1, a1);
                PrimitiveConstraint bd = new XltY(b1, d1);
                PrimitiveConstraint ca = new XltY(c1, a1);
                PrimitiveConstraint cd = new XltY(c1, d1);
                PrimitiveConstraint db = new XltY(d1, b1);
                PrimitiveConstraint dc = new XltY(d1, c1);
                
                ArrayList<PrimitiveConstraint> orList = new ArrayList<>();
                orList.add(new And(new PrimitiveConstraint[]{ab, bd, dc}));
                orList.add(new And(new PrimitiveConstraint[]{ac, cd, db}));
                orList.add(new And(new PrimitiveConstraint[]{ba, ac, cd}));
                orList.add(new And(new PrimitiveConstraint[]{bd, dc, ca}));
                orList.add(new And(new PrimitiveConstraint[]{ca, ab, bd}));
                orList.add(new And(new PrimitiveConstraint[]{cd, db, ba}));
                orList.add(new And(new PrimitiveConstraint[]{db, ba, ac}));
                orList.add(new And(new PrimitiveConstraint[]{dc, ca, ab}));
                store.impose(new Or(orList));
            }
        }
        
        Constraint different = new Alldifferent(vars); 
        store.impose(different);
        
        //consistency check but if this is true, it still could be that it's inconsistent
        if(!store.consistency()){
            System.out.println("1");
            return circle;
        }
        
        Search<IntVar> label = new DepthFirstSearch<>(); 
        SelectChoicePoint<IntVar> select = new SimpleSelect<>(vars, new SmallestDomain<IntVar>(), new IndomainMin<>()); 
        if(!label.labeling(store, select)){
            System.out.println("2");
            return circle;
        }
        
        ArrayList<Character> circ = new ArrayList<>();
        for(int i = 0; i<size; i++)
            circ.add('0');
        
        for(int j = 0; j<size; j++)
            circ.set(vars[j].value()-1,(char) (j+97));
        
        return new Circle(circ);
    }
    
    //a greedy heuristic to construct a circle from the quartets without backtracking
    public static Circle greedy(ArrayList<Quartet> quartets, int size){
        Circle circle = new Circle(size);
        
        //first make 2 lists, 1 where there is 1 quartet for those 4 taxa, the other 2 quartets for those 4 taxa
        ArrayList<Quartet> one = new ArrayList<>();
        ArrayList<Quartet> two = new ArrayList<>();
        for(int i = 0; i<quartets.size(); i++){
            for(int j = i+1; j<quartets.size(); j++){
                if(quartets.get(i).sameTaxa(quartets.get(j))){
                    two.add(quartets.get(i));
                    two.add(quartets.get(j));
                }
            }
            if(!two.contains(quartets.get(i)))
                one.add(quartets.get(i));
        }
        
        if(one.size() + two.size() != quartets.size())
            System.out.println("Greedy error!");
        
        ArrayList<Quartet[]> whole = new ArrayList<>();
        if(two.size() > 0)
            whole = Solver.sortLists(one, two, two.get(0));
        else
            whole = Solver.sortLists(one, two, one.get(0));
        
        for(int i = 0; i<whole.size(); i++){
            char a = 0, b=0, c=0, d=0;
            if(whole.get(i)[1] != null){
                 // the ordering on the circle is: a b d c
                if(whole.get(i)[1].pairContains(true,whole.get(i)[0].getPair1()[0]))
                    a = whole.get(i)[0].getPair1()[0];
                else if(whole.get(i)[1].pairContains(true,whole.get(i)[0].getPair1()[1]))
                    a = whole.get(i)[0].getPair1()[1];

                if(whole.get(i)[0].getPair1()[0] != a)
                    b = whole.get(i)[0].getPair1()[0];
                else if(whole.get(i)[0].getPair1()[1] != a)
                    b = whole.get(i)[0].getPair1()[1];

                if(whole.get(i)[1].getPair1()[0] != a)
                    c = whole.get(i)[1].getPair1()[0];
                else if(whole.get(i)[1].getPair1()[1] != a)
                    c = whole.get(i)[1].getPair1()[1];

                if(whole.get(i)[0].getPair2()[0] != a && whole.get(i)[0].getPair2()[0] != b && whole.get(i)[0].getPair2()[0] != c)
                    d = whole.get(i)[0].getPair2()[0];
                else if(whole.get(i)[0].getPair2()[1] != a && whole.get(i)[0].getPair2()[1] != b && whole.get(i)[0].getPair2()[1] != c)
                    d = whole.get(i)[0].getPair2()[1];
            } else{
                // the ordering on the circle is: a-b-d-c or a-b-c-d
                a = whole.get(i)[0].getPair1()[0]; 
                b = whole.get(i)[0].getPair1()[1]; 
                c = whole.get(i)[0].getPair2()[0]; 
                d = whole.get(i)[0].getPair2()[1]; 
            }

                if(circle.size() <4){
                    if(!circle.isEmpty() || !(circle.add(0,b) && circle.add(1,a) && circle.add(2,c) && circle.add(3,d)))
                        System.out.println("Some greedy error!!!!!!!");
                }else{
                    if(circle.contains(whole.get(i)[0].getPair1()[0]) && circle.contains(whole.get(i)[0].getPair1()[1]) && circle.contains(whole.get(i)[0].getPair2()[0]) && circle.contains(whole.get(i)[0].getPair2()[1])){
                        //if all taxa are already on the circle, check if the two quartets are also on the circle
                        if(whole.get(i)[1] != null){
                            if(!whole.get(i)[1].isOnCircle(circle) && !whole.get(i)[0].isOnCircle(circle)){
                                circle.clear();
                                return circle;
                            }
                        } else {
                            if(!whole.get(i)[0].isOnCircle(circle)){
                                circle.clear();
                                return circle;
                            }
                        }
                    }else{
                        ArrayList<Character> taxa = circle.getTaxaNotOnCircle(whole.get(i)[0]);
                        int aPos = -1, bPos = -1, cPos = -1, dPos = -1;
                        if(!taxa.contains(a))
                            aPos = circle.position(a);
                        if(!taxa.contains(b))
                            bPos = circle.position(b);
                        if(!taxa.contains(c))
                            cPos = circle.position(c);
                        if(!taxa.contains(d))
                            dPos = circle.position(d);
                        if(taxa.size() == 1){
                            if(aPos < 0){   //a must be between b and c
                                if((bPos < cPos && cPos < dPos) || (cPos < dPos && dPos < bPos) || (dPos < bPos && bPos < cPos))
                                    circle.add(cPos, a);
                                else if((bPos < dPos && dPos < cPos) || (cPos < bPos && bPos < dPos) || (dPos < cPos && cPos < bPos))
                                    circle.add(bPos, a);
                                else
                                    System.out.println("Some greedy error1");
                            } else if(bPos < 0){    //b must be between a and d
                                if((aPos < cPos && cPos < dPos) || (cPos < dPos && dPos < aPos) || (dPos < aPos && aPos < cPos))
                                    circle.add(aPos, b);
                                else if((aPos < dPos && dPos < cPos) || (cPos < aPos && aPos < dPos) || (dPos < cPos && cPos < aPos))
                                    circle.add(dPos, b);
                                else
                                    System.out.println("Some greedy error2");
                            } else if(cPos < 0){    //c must be between a and d
                                if((aPos < bPos && bPos < dPos) || (bPos < dPos && dPos < aPos) || (dPos < aPos && aPos < bPos))
                                    circle.add(aPos, c);
                                else if((aPos < dPos && dPos < bPos) || (bPos < aPos && aPos < dPos) || (dPos < bPos && bPos < aPos))
                                    circle.add(dPos, c);
                                else
                                    System.out.println("Some greedy error3");
                            } else if(dPos < 0){    //d must be between b and c
                                if((aPos < bPos && bPos < cPos) || (bPos < cPos && cPos < aPos) || (cPos < aPos && aPos < bPos))
                                    circle.add(cPos, d);
                                else if((aPos < cPos && cPos < bPos) || (bPos < aPos && aPos < cPos) || (cPos < bPos && bPos < aPos))
                                    circle.add(bPos, d);
                                else
                                    System.out.println("Some greedy error4");
                            } else
                                System.out.println("Some greedy error5");
                        } else
                            System.out.println("I hope this doesn't happen");
                    }
                }
        }
        
        return circle;
    }
    
    private static ArrayList<Quartet[]> sortLists(ArrayList<Quartet> one, ArrayList<Quartet> two, Quartet q){
        ArrayList<Quartet[]> whole = new ArrayList<>();
        for(int i = 0; i < two.size(); i = i+2)
            whole.add(new Quartet[]{two.get(i), two.get(i+1)});
        for(int j = 0; j < one.size(); j++)
            whole.add(new Quartet[]{one.get(j), null});
        
        Solver.sortList2(whole, q);
        return whole;
    }
    
    private static void sortList2(ArrayList<Quartet[]> list, Quartet q){
        if(list.size() > 1){
            Quartet[] first = list.get(0);
            ArrayList<Quartet[]> lessEqual = new ArrayList<>();
            ArrayList<Quartet[]> more = new ArrayList<>();
            for(int i = 1; i<list.size(); i++){
                if(list.get(i)[0].similarity(q) <= first[0].similarity(q))
                    lessEqual.add(list.get(i));
                else
                    more.add(list.get(i));
            }
            Solver.sortList2(lessEqual, q);
            Solver.sortList2(more, q);

            list.clear();
            list.addAll(more);
            list.add(first);
            list.addAll(lessEqual);
        }
    }
    
    private static char[] deleteLast(char[] list){
        char[] l = new char[list.length-1];
        System.arraycopy(list, 0, l, 0, l.length);
        return l;
    }
    
    private static char[]insert(char[] list, char c, int position){
        char[] l = new char[list.length+1];
        for(int i = 0; i<l.length; i++){
            if(i == position)
                l[i] = c;
            else if(i<position)
                l[i] = list[i];
            else
                l[i] = list[i-1];
        }
        return l;
    }
    
    //make table in which the numbers of the corresponding places in the set a char is
    private static ArrayList<ArrayList<Integer>> makeTable(ArrayList<Quartet> quartets, int size){
        ArrayList<ArrayList<Integer>> positions = new ArrayList<>();
        for(int t = 0; t<size; t++){
            for(int u = 0; u < quartets.size(); u++){
                //97 is 'a'
                char c = (char) (t+97);
                if(quartets.get(u).contains(c))
                    positions.get(t).add(u);
            }
        }
        return positions;
    }
    
    public static boolean subset(int subsetSize, ArrayList<Quartet> quartets, int size){
        char[] alphabet = DenseSetGenerator.generateAlphabet(size);
        ArrayList<ArrayList<Integer>> positions = makeTable(quartets, size);

        int[] alphabetPointer = new int[subsetSize];
        for(int i = 0; i<alphabetPointer.length; i++)
            alphabetPointer[i] = i;
        
        int[] positionsPointer = new int[subsetSize];
        
        boolean done = false;    
        while(!done){
            ArrayList<Quartet> subset = new ArrayList<> ();
            for(int j = 0; j<subsetSize; j++){
                
            }
        }
        
//        for(int x=0; x<size; x++){
//            for(int y=0; y<s; y++){
//                System.out.println("x: " + x + " y: " + y + " value: " + positions[x][y]);
//            }
//        }
//        
//        for(int i = 0; i<alphabet.length-3; i++){   //abcdef -> abcde - abcdf - abcef - abdef - acdef - bcdef
//            for(int j = i+1; j< alphabet.length-2;j++){
//                for(int k = j+1; k<alphabet.length-1; k++){
//                    for(int l = k+1; l<alphabet.length; l++){
//                        for(int m = l+1; m<alphabet.length; m++){
//                            
//                            int n=0, o=0, p=0, q=0, r=0;
//                            ArrayList<Quartet> subset = new ArrayList<> ();
//                            //find the quartets for the subset
//                            while(n<positions[0].length && o<positions[1].length && p<positions[2].length && q<positions[3].length && r<positions[4].length){
////                                System.out.println("n= " + n + " o= " + o + " p= " + p + " q= " + q + " r= " + r);
//                                if((positions[i][n] == positions[j][o] && positions[i][n] == positions[k][p] && positions[i][n] == positions[l][q])){
//                                    subset.add(quartets.get(positions[i][n]));
//                                    n++; o++; p++; q++;
//                                } else if(positions[i][n] == positions[j][o] && positions[i][n] == positions[k][p] && positions[i][n] == positions[m][r]){
//                                    subset.add(quartets.get(positions[i][n]));
//                                    n++; o++; p++; r++;
//                                } else if(positions[i][n] == positions[j][o] && positions[i][n] == positions[l][q] && positions[i][n] == positions[m][r]){
//                                    subset.add(quartets.get(positions[i][n]));
//                                    n++; o++; r++; q++;
//                                } else if(positions[i][n] == positions[k][p] && positions[i][n] == positions[l][q] && positions[i][n] == positions[m][r]){
//                                    subset.add(quartets.get(positions[i][n]));
//                                    n++; r++; p++; q++;
//                                } else if(positions[j][o] == positions[k][p] && positions[j][o] == positions[l][q] && positions[j][o] == positions[m][r]){
//                                    subset.add(quartets.get(positions[j][o]));
//                                    o++; r++; p++; q++;
//                                } else{
//                                    ArrayList<Integer> temp = new ArrayList<>();
//                                    temp.add(positions[i][n]);
//                                    temp.add(positions[j][o]);
//                                    temp.add(positions[k][p]);
//                                    temp.add(positions[l][q]);
//                                    temp.add(positions[m][r]);
////                                    for(int z: temp){
////                                        System.out.println("Temp: " + z);
////                                    }
//                                    int min = Collections.min(temp);
////                                    System.out.println("min: " + min);
//                                    if(positions[i][n] == min && n-1<positions[0].length)
//                                        n++;
//                                    else if(positions[j][o] == min && o-1<positions[1].length)
//                                        o++;
//                                    else if(positions[k][p] == min && p-1<positions[2].length)
//                                        p++;
//                                    else if(positions[l][q] == min && q-1<positions[3].length)
//                                        q++;
//                                    else
//                                        r++;
//                                }
//                            }
//                            //check if the subset is on a circle
//                            if(bruteForce(subset, size).isEmpty())
//                                return false;
//                        }
//                    }
//                }
//            }
//        }
//        
        return true;
    }
    
    public static void main(String[] args){
//        char[] alphabet = new char[]{'a', 'b', 'c', 'd'};
//        ArrayList<char[]> p = permutations(alphabet);
//        for(char[] c: p){
//            System.out.println(Character.toString(c[0]) + Character.toString(c[1])
//                    + Character.toString(c[2]) + Character.toString(c[3]));
//        }
        
//        System.out.println(makeTable(DenseSetGenerator.randomSet(6, 2),6)[0].length);
        
//            ArrayList<ArrayList<Quartet>> set = DenseSetGenerator.allSets(5);
//            ArrayList<ArrayList<Quartet>> newSet = checkAll(set, 5);
//            int i = 0;
//            for(ArrayList<Quartet> list: newSet){
//                i++;
//                System.out.println("List " + i);
//                for(Quartet q: list){
//                    System.out.println(q);
//                }
//            }
        
        //THE COUNTEREXAMPLE
        ArrayList<Quartet> q = new ArrayList<>();
//        q.add(new Quartet(new char[]{'a', 'b'}, new char[]{'c', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'c'}, new char[]{'b', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'b'}, new char[]{'c', 'e'}));
//        q.add(new Quartet(new char[]{'a', 'b'}, new char[]{'c', 'f'}));
//        q.add(new Quartet(new char[]{'a', 'b'}, new char[]{'e', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'e'}, new char[]{'b', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'b'}, new char[]{'f', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'b'}, new char[]{'e', 'f'}));
//        q.add(new Quartet(new char[]{'a', 'c'}, new char[]{'e', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'c'}, new char[]{'f', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'c'}, new char[]{'e', 'f'}));
//        q.add(new Quartet(new char[]{'a', 'd'}, new char[]{'e', 'f'}));
        q.add(new Quartet(new char[]{'c', 'b'}, new char[]{'e', 'd'}));
//        q.add(new Quartet(new char[]{'c', 'b'}, new char[]{'f', 'd'}));
//        q.add(new Quartet(new char[]{'c', 'b'}, new char[]{'e', 'f'}));
//        q.add(new Quartet(new char[]{'d', 'b'}, new char[]{'e', 'f'}));
//        q.add(new Quartet(new char[]{'c', 'd'}, new char[]{'e', 'f'}));
//        q.add(new Quartet(new char[]{'a', 'f'}, new char[]{'c', 'd'}));
//        q.add(new Quartet(new char[]{'a', 'e'}, new char[]{'b', 'c'}));
//        q.add(new Quartet(new char[]{'b', 'd'}, new char[]{'c', 'e'}));
        q.add(new Quartet(new char[]{'b', 'c'}, new char[]{'a', 'd'}));
        q.add(new Quartet(new char[]{'c', 'b'}, new char[]{'e', 'a'}));
        q.add(new Quartet(new char[]{'b', 'd'}, new char[]{'a', 'e'}));
        q.add(new Quartet(new char[]{'c', 'd'}, new char[]{'e', 'a'}));
        System.out.println(bruteForce(q,5));
//        System.out.println(divide5(q,6));
    }
    
    
}
